% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[11pt]{article} % use larger type; default would be 10pt

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)

%%% Examples of Article customizations
% These packages are optional, depending whether you want the features they provide.
% See the LaTeX Companion or other references for full information.

%%% PAGE DIMENSIONS
\usepackage{geometry} % to change the page dimensions
\geometry{a4paper} % or letterpaper (US) or a5paper or....
% \geometry{margins=2in} % for example, change the margins to 2 inches all round
% \geometry{landscape} % set up the page for landscape
%   read geometry.pdf for detailed page layout information

\usepackage{graphicx} % support the \includegraphics command and options

% \usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

%%% HEADERS & FOOTERS
\usepackage{lastpage}
\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\setlength{\headheight}{15pt}
%\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{}\rfoot{}

%%% SECTION TITLE APPEARANCE
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)


%%% ToC (table of contents) APPEARANCE
\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!

%%% END Article customizations

\usepackage{listings}


%%% \usepackage[swedish]{babel}



%%% The "real" document content comes below...

\title{An approach to mobile communication with Software Defined Radio}
\author{Erik Persson} 

\date{Luleå University of Technology\\2013-06-08}%Luleå Tekniska Universitet\\2011-xx-xx} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 


\begin{document}

\pagestyle{empty}
\maketitle
\thispagestyle{empty}

\newpage
%\vspace*{\fill}
\mbox{}\vfill
\begin{abstract}
\noindent

Synchronizing a mobile device to the host system is an important feature for all mobile communication systems. In WCDMA, a Radio Access Technology (RAT) used in a third generation mobile telecommunication system called UMTS, the synchronisation process is divided in a number of steps. This thesis project covers the necessary steps in order to synchronise and receive broadcast messages from a WCDMA radio base station by creating a software WCDMA receiver capable of tuning in on WCDMA radio base stations, finding radio frames, detecting coding schemes used by the base station and finally being able to capture and decode broadcast messages transmitted by the base station and in the meantime also evaluate the usage of software defined radio within WCDMA. 

This involves performing tasks traditionally performed in hardware such as processing signals, detecting slot and frame boundaries, descrambling, performing phase compensation, detecting scrambling codes, decoding channels, decoding convolutionally encoded bit strings, performing CRC calculations and much more in order to turn the signal received by a universal software radio peripheral into decoded bits.

This thesis project was carried out, in-house at Neava AB in Luleå, Sweden.





\end{abstract}
\mbox{}\vfill
\mbox{}\vfill
\newpage

\mbox{}\vfill
\subsection*{Preface}
For me, studying WCDMA with Software Defined Radio has been an interesting journey, coming from a background with no previous knowledge in signal processing or radio technology. I want to thank Staffan Johansson at Neava AB for offering me the chance of playing around with this technology and the rest of the Neava staff for helping me out during this project. I would also like to thank my wife and kids for their patience and support.

\mbox{}\vfill
\mbox{}\vfill
\newpage

\tableofcontents

\newpage

\pagestyle{fancy}
\lhead{An approach to mobile communication with Software Defined Radio}\chead{}\rhead{2013-06-08}
\lfoot{}\cfoot{\thepage (\pageref{LastPage})}\rfoot{}
\setcounter{page}{1}
\section{Introduction}
\label{sec:introduction}
Mobile communication involves huge computational demands, especially for the physical layer. As a result of this, the physical layer algorithms are often realised onto specially designed hardware, eg. ASICs (Application Specific Integrated Circuits), built for a specific physical layer protocol. As mobile communication evolves, the complexity- and the amount- of physical layer protocols are increasing. Mobile devices, often light weight hand-held terminals with limited power supplies, are facing an increased demand to support an increasing amount of protocol stacks. From this, the idea of performing parts- and/or all- of the physical layer operations in software started to arise, and so the first ideas of Software Defined Radio~\cite{ref:SDRBook} (SDR) were born.

SDR offers a low cost solution to research and development within the field of radio technology. SDR enables development of radio receivers and/or transmitters without the requirement of creating new specially designed hardware. The benefits of SDR makes the technique well suited for use in studying different physical layer protocols.

A key functionality within all physical layer protocols is to synchronize a mobile device to the host system. In WCDMA~\cite{ref:convergence}\cite{ref:WCDMA} (the Radio Access Technology (RAT) used within UMTS; a 3rd generation telecommunication system) being synchronized means to be able to read the broadcast messages transmitted by a Radio Base Station (RBS)/WCDMA cell. 

The synchronisation is performed in a number of steps. The first step is to locate any possible cells within a set of frequency bands. This is done by performing a RSSI (Received Signal Strength Indicator) scan. When a candidate cell has been detected the synchronisation is performed in three steps: Slot synchronisation, Frame synchronisation and Scrambling code identification. First when these steps have been carried out the mobile device can try to read the broadcast messages transmitted by the cell.

In this thesis project the goals are to evaluate the usage of Software Defined Radio for use in
mobile communication. This should be done by creating software for a Universal
Software Radio Peripheral in order to synchronize against WCDMA cells. By being
synchronized means, to be able to read the broadcast messages transmitted from a base-station. This document describes UMTS and WCDMA systems in short, the synchronisation process, channel decoding and the software implementation done during this thesis project. The focus will be on the physical layer of WCDMA~\cite{ref:ts25201}\cite{ref:ts25211}\cite{ref:ts25212}\cite{ref:ts25213}\cite{ref:ts25214}\cite{ref:ts25215}. The intention with this report is not to explain SDR in detail since others have already done this~\cite{ref:SDRBook}\cite{ref:SDRBook2}.

The software radio device used in this thesis is an USRP N210 from Ettus Research~\cite{ref:ettusweb} which is used together with the GNU Radio software~\cite{ref:gnuradioweb}.

This thesis project were done in-house at Neava AB, in Luleå, Sweden. Neava is a software company mainly focusing on embedded real time systems within the sector of mobile telecommunications.

%technical specification of the WCDMA physical layer:
%25.201 Physical layer - general description (V7.3.0, 2007-05)
%25.211 Physical channels and mapping of transport channels
%onto physical channels (FDD) (V9.2.0, 2010-09)
%25.212 Multiplexing and channel coding (FDD) (V7.7.0,2007-11)
%25.213 Spreading and modulation (FDD) (V9.2.0, 2010-09)
%25.214 Physical layer procedures (FDD) (V7.12.0, 2009-05)
%25.215 Measurements (FDD) 

%GNU Radio \emph{http://www.gnuradio.org}\cite{ref:gnuradioweb}

%In this thesis project the goals are to ...

%The goal of this thesis project is to evaluate the usage of Software Defined Radio for use in mobile communication. This should be done by creating software for a Universal Software Radio Peripheral in order to synchronize against WCDMA cells. By being synchronized means, to be able to read the broadcast messages from a base-station. This document describes UMTS and WCDMA systems in short, the synchronisation process, channel decoding and the software implementation done during this thesis project.

%This thesis project were done in-house at Neava AB, in Luleå, Sweden. Neava is a software company mainly focusing on embedded real time systems within the sector of mobile telecommunications.

%\subsection{Background}
%Synchronizing a mobile device to the host system is an important feature for all mobile communication systems.

%In WCDMA a set of frequency bands are used, each one allocating 5 Mhz. In order to synchronize against a cell multiple steps are required. The first step is to locate an active cell in the different bands. In order to locate cells, a RSSI (Received Signal Strength Indicator) scan is performed. When an active cell has been detected the synchronisation is performed in three steps: Slot synchronisation, Frame synchronisation and Scrambling code identification.

%When the scrambling code for the given cell has been identified it's possible to decode the signals from the base station.

%The software radio device used in this thesis is an USRP N210 from Ettus Research which is used together with the GNU Radio software.


\newpage

\section{Method}
The work done during this thesis project were divided into three phases: 
\begin{itemize}
 \item Pre-studies - Literature studies in order to get a grip of the subject. Literature used were \emph{Convergence Technologies for 3G Networks IP, UMTS, EGPRS and ATM}, \cite{ref:convergence} and \emph{WCDMA Design Handbook}, \cite{ref:WCDMA}. These two books were used in order to write the section \emph{Introduction to WCDMA} (Sec.~\ref{sec:introWCDMA}). Parts of the 3GPP specifications~\cite{ref:ts25201}\cite{ref:ts25211}\cite{ref:ts25212}\cite{ref:ts25213}\cite{ref:ts25214}\cite{ref:ts25215}\cite{ref:ts25302} have also been studied, but mostly during the implementation phase. The 3GPP specification were also used in order to write the more technically detailed sections of the report.
 
 \item Implementation - The implementation phase involved implementing a software radio receiver for synchronizing against WCDMA cells, using GNU radio, C++ and Python. It also involved generating the radio signals in order to verify the implementation of the receiver.\\
 
 \item Report writing - The writing of the report has been a constant process during the entire project and the structure of the report mainly follows the structure of the workflow.
\end{itemize}



\subsection{Tools and hardware}
This section lists a few of the tools used during this thesis project. All software were at the time available for free (open source licence / other public licence) and available for multiple operating systems.

\subsubsection{Software Defined Radio}
In short, SDR (Software Defined Radio) is often described as \emph{the technique of getting code as close to the antenna as possible. It turns radio hardware problems into software problems}. In reality it means that parts of the radio receiver/transmitter chain has been replaced by software.
A more technical definition of SDR is defined by \emph{The Wireless Innovation Forum}\cite{ref:WIF}, where differences are made between software controlled- and software defined- radio, and is as follows (\emph{SDRF Cognitive Radio Definitions}\cite{ref:SDRDef}):

\begin{itemize}
\item Software Controlled \\
Software controlled refers to the use of software processing within the radio system or
device to select the parameters of operation.

\item Software Defined \\
Software defined refers to the use of software processing within the radio system or
device to implement operating (but not control) functions.

\item Software Controlled Radio \\
Radio in which some or all of the physical layer functions are Software Controlled.

\item Software Defined Radio (SDR) \\
Radio in which some or all of the physical layer functions are Software Defined.
\end{itemize}


A basic SDR may consist of some sort of computer (personal or embedded), connected to a device capable of sampling radio signals. The samples are delivered to the computer and software is used to perform the actual signal processing.


\subsubsection{GNU Radio}
GNU radio is an open source software development toolkit for creating signal processing software. Basically it consists of signal processing blocks that can be combined into flow charts that processes signals. The signal processing blocks are written in C++ and Python code is used in order to combine the blocks into flow charts. It comes with a set of signal processing blocks for common signal processing tasks and new blocks are easily written in C++ by extending the predefined classes. 

GNU Radio also includes a graphical tool, \emph{GNU Radio Companion} (Fig.~\ref{fig:gnuradio}), with which flowcharts can be created by dragging and dropping signal processing blocks. The tool then creates the python code that combines the signal processing blocks. 

For more information about GNU Radio and installation instructions see:\\ \emph{http://www.gnuradio.org}\cite{ref:gnuradioweb}

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/gnuradio.png}
	\caption{Image of \emph{gnuradio-companion}, a graphical tool for creating signal processing software.}
	\label{fig:gnuradio}
\end{figure*}

\subsubsection{USRP N210}

The USRP N210 device from \emph{Ettus Research LLC} is a device for receiving and transmitting radio signals using a computer with a Gigabit Ethernet connection. Various daughter boards can be plugged in, in order to use the device on different frequency bands. The entire design of the hardware is open source, including the daughter boards.

The device can be tuned in on different carrier frequencies and sampling rates. It performs the downscaling of the signal from the specified carrier frequency down to baseband. The signal is then sampled at the specified sampling rate and the samples are transmitted over the Gigabit Ethernet interface to a computer for further processing.
 
The N210 can be used together with GNU Radio, for more information and installation instruction see \emph{http://www.ettus.com}\cite{ref:ettusweb}\\

\noindent USRP N210 SDR specification (from Ettus Research web page~\cite{ref:ettusweb}, 2011-08-17)
\begin{itemize}
 \item 50 MHz of instantaneous RF bandwidth
 \item Gigabit Ethernet connectivity
 \item MIMO capable - Requires two or more USRP N210 devices as motherboard has one daughterboard slot
 \item Onboard FPGA processing
 \item FPGA: Xilinx Spartan XC3SD3400A
 \item ADCs: 14-bits 100 MS/s
 \item DACs: 16-bits 400 MS/s
 \item Ability to lock to external 5 or 10 MHz clock reference
 \item TCXO Frequency Reference (~2.5ppm)
 \item Optional internal GPS locked reference oscillator
 \item FPGA code can only be changed with the paid version of the Xilinx® ISE® Design Suite tools
\end{itemize}
The device used for receiving and sample the signals is an \emph{USRP N210} from \emph{Ettus Research LLC} with WBX daughter boards having a coverage of 50 MHz to 2.2 GHz. 

\newpage

\section{Introduction to UMTS and WCDMA}\label{sec:introWCDMA}
The following sections contains a short introduction to UMTS and WCDMA needed in order to understand the basic concepts.

\subsection{UMTS}
Universal Mobile Telecommunications System (UMTS) is the name of a third generation (3G) telecommunication system that is being defined by the 3rd Generation Partnership Project (3GPP). UMTS consists of two Radio Access Technologies (RATs), WCDMA and GSM/EDGE, where GSM/EDGE is an evolved version of the 2G GSM system.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/UMTS_overview.png}
	\caption{High level representation of a UMTS network.}
	\label{fig:UMTSOverview}
\end{figure*}

Figure~\ref{fig:UMTSOverview} displays the structure of a UMTS network. A user equippment (UE) is connected to a radio base station (RBS). The RBS is connected to a radio network controller (RNC), and the RNC is connected to the core network (CN) and optionally to other RNCs. The figure also displays the interfaces that connects the different devices. The different interfaces are often referred to as Uu between UE and RBS, Iub between RBS and RNC, Iu between RNC and CN, and as Iur for RNC to RNC. UMTS networks supports both circuit switched and packet switched data exchange.


\subsection{WCDMA}
WCDMA (Wideband Code Division Multiple Access) is one of the RATs used in UMTS networks for communication between UEs and RBSs. WCDMA exists in two different forms FDD (Frequency Division Duplex) and in TDD (Time Division Duplex). In FDD the uplink (UL) and downlink (DL) are separated by frequency, compared to TDD where the UL and DL are separated in the time domain. Throughout this document when referring to WCDMA it means WCDMA FDD, unless WCDMA TDD is specifically stated.

When sending signals through a shared physical medium, as the radio air interface, it is important to separate different signals or streams of data from each other. There exists numerous different techniques for doing this. CDMA, FDMA and TDMA are probably some of the most common ways of dividing a shared medium between different users. As the name implies, WCDMA is based on CDMA, performed in wideband.

\begin{itemize}
\item FDMA - Frequency Division Multiple Access, divides the frequency usage between the different users.
\item TDMA - Time Division Multiple Access, the shared medium is divided in the time domain between the different users. 
\item CDMA - Code Division Multiple Access, separates the different signals by encoding them with special codes. 
\end{itemize}

 
\subsection{The WCDMA stack}
This section gives a brief explanation of the WCDMA stack. The stack is separated into two sets: the access stratum (AS) and the non access stratum (NAS). The AS mainly handles signalling and data transportation while the NAS interprets and handles the transported data.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=80mm]{images/WCDMAStack.png}
	\caption{The WCDMA stack.}
	\label{fig:WCDMAStack}
\end{figure*}

\subsubsection{RRC}
The radio resource control (RRC) layer is responsible of establishing, maintaining and releasing radio resource connections between the UE and the CN. The RRC controls the lower layers of the WCDMA stack.

\subsubsection{RLC}
The radio link control (RLC) layer provides transport services between RLC entities in the UE and in the RNC. Three modes are supported: transparent, unacknowledged and acknowledged. In transparent mode the RLC passes packets directly without adding any extra header information. This requires that the packets being sent is of appropriate size. In unacknowledged mode the RLC passes packets onwards without ensuring delivery. The data can be concatenate and padded in order to fit appropriate packet size. Unacknowledged mode also contains some ciphering functionality. The acknowledged mode provides the same services as the unacknowledged mode with the addition of retransmission control, discarding of duplicated packets and in sequence delivery.

\subsubsection{MAC}
The medium access control (MAC) layer is responsible of mapping logical channels onto transport channels. This mapping can change dynamically as the characteristics of the network or the user changes. The MAC layer is also responsible of reporting the bandwidth usage back to RRC.

\subsubsection{PHY}
PHY, the physical layer, is responsible mapping transport channels onto physical channels and the transmission/reception of the physical channels over the air interface. The physical layer also deliver measurement reports back to the RRC.

\subsection{Chips, slots and radio frames}
In WCDMA each radio frame is 10 ms long. Each frame consists of 15 slots. Each slot consists of 2560 chips. Giving a total of 38400 chips per frame or, in other words, a chip rate of 3.84 million chips per second. A chip is the smallest whole information carrying part of the signal, although it is also possible and common to use fractions of chips, half-chip and quarter chips etc.

\subsection{Modulation and complex signals}
There exists three basic modulation techniques: frequency modulation (FM), amplitude modulation, and phase modulation. WCDMA uses phase modulation and for some channels a combination of phase and amplitude modulation. When dealing with phase and amplitude modulation of a sinusoidal it is practical to represent the signal in the complex plane, often referred to as the I/Q plane. Each sample consists of one real part, I, and one imaginary part Q. Figure \ref{fig:IQSignals} illustrates how the amplitude and phase maps to the I and Q parts. For further reading on IQ signals the web tutorial: \emph{What is I/Q Data?} from National Instruments is recommended  \cite{ref:IQSignals}.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=50mm]{images/IQSignals.png}
	\caption{Representation of a signal in the IQ-plane}
	\label{fig:IQSignals}
\end{figure*}


\subsection{WCDMA codes}
The codes covered in this section are described further in the 3GPP technical specification 25.213~\cite{ref:ts25213} which can be acquired from the 3GPP website~\cite{ref:3gppweb}). The information about the properties of the codes are collected from the \emph{WCDMA Design Handbook} \cite{ref:WCDMA} which explains the properties in greater detail.

For all codes declared in the following subsections, the leftmost chip in a sequence corresponds to the chip transmitted first in time.


\subsubsection{Correlation}\label{sec:correlation}
Correlation~\cite{ref:correlation} is widely used within WCDMA as a matching filter. The following formula is used for correlation of two sequences, $s_1$ and $s_2$, where $s_1[k]$ and $s_2[k]$ corresponds to the $(k+1)$:th value of the respective sequence:
$$ R[m] = \sum^{N-1}_{i=0} (s_1[i] s_2^{*}[i+m]) ,$$
where $N$ is the length of $s_1$, $s_2^*[n]$ is the complex conjugate of $s_2[n]$ and $m$ is the correlation offset into the sequence $s_2$.
The result $R[m]$ may be used to judge of how well $s_1$ matches $s_2$ at offset $m$.


\subsubsection{Primary synchronisation code}\label{sec:psc}
The primary synchronisation code (PSC) is transmitted on the primary synchronisation channel (P-SCH) at the first 256 chips of each slot. The purpose of the P-SCH is to ease the detection of the slots boundaries. According to \cite{ref:ts25213} the PSC is constructed as a so-called generalised hierarchical Golay sequence and is constructed to have good auto-correlation properties, in short meaning that it will generate large peaks when perfectly aligned and correlated against itself and almost no peak otherwise.

The PSC is defined as:
\begin{eqnarray*}
  a & = & [x_1, x_2, x_3, ..., x_{16}]\\
  & = & [1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1]\\
  PSC & = & (1 + j)[a, a, a, -a, -a, a, -a, -a, a, a, a, -a, a, -a, a, a]
\end{eqnarray*}

\subsubsection{Secondary synchronisation codes}\label{sec:ssc}
The secondary synchronisation codes (SSC) are transmitted on the secondary synchronisation channel (S-SCH) at the first 256 chips of each slot. There exists 16 different SSCs and they are used to create the 64 different S-SCH sequences defined by the 3GPP. The purpose of the S-SCH is to ease the detection of the frame boundaries and also to identify what scrambling code group that a particular cell belongs to.

The SSCs $\lbrace SSC_1, SSC_2, ... , SSC_{16}\rbrace$ are constructed by combining a set of so-called Hadamard sequences with the sequence $z$ defined as:
\begin{eqnarray*}
  z & = & [b, b, b, -b, b, b, -b, -b, b, -b, b, -b, -b, -b, -b, -b]\\
  b & = & [x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, -x_9, -x_{10}, -x_{11}, -x_{12}, -x_{13}, -x_{14}, -x_{15}, -x_{16}]
\end{eqnarray*}
where $\lbrace x_1, x_2, ..., x_{16}\rbrace$ are the same as the $\lbrace x_1, x_2, ..., x_{16}\rbrace$ used in the definition of the PSC in the previous section.

$$SSC_k = (1+j)\times[z(0) h_k(0), z(1) h_k(1), z(2) h_k(2), z(3) h_k(3), ..., z(255) h_k(255)]$$ for $1 \leq k \leq 16$ where $h_k(i)$ denotes the i:th symobol of the k:th Hadamard sequence and $z(i)$, the i:th symbol of the z sequence.

The Hadamard sequences are obtained from the rows of a recursively created matrix, $H_8$, defined as:
$$H_0=1$$
$$
H_j \left[
  \begin{array}{ c c }
     H_{j-1} & H_{j-1} \\
     H_{j-1} & -H_{j-1}
  \end{array} \right], j > 0.
$$

Finally $h_k$ is defined as $h_k = H_8(16*(k-1))$, where $H_8(i)$ denotes the i:th row from the matrix $H_8$.

\subsubsection{Channelisation codes}
The purpose of the channelisation codes are to spread and separate the different channels transmitted from a RBS or a UE. One important property of channelisation codes are orthogonality, meaning that the sum of the position wise multiplication of two codes is equal to zero. This can be compared to an orthogonal system in a three-dimensional space where each dimension is completely independent of the others.

The formula below describes the relationship of the channelisation codes:
\begin{eqnarray*}
C_i & = & [C_{i0}, C_{i1}, C_{i2}, ... , C_{i(N-1})],\\
C_j & = & [C_{j0}, C_{j1}, C_{j2}, ... , C_{j(N-1})],
\end{eqnarray*}
where $C_{in}$ $\epsilon$ $\lbrace+1, -1\rbrace$, $C_{jn}$ $\epsilon$ $\lbrace+1, -1\rbrace$, $0 \leq n \leq N-1$ and $N$ defines the chip length of each code. The codes are orthogonal to each other if the following statement holds:

$$
\sum^{N-1}_{n=0}C_{in}C_{jn} = 
\left\lbrace
  \begin{array}{ c c }
     0 & i \neq j \\
     N & i = j
  \end{array} 
\right.
.$$


The codes are created from a so-called orthogonal variable spreading factor (OVSF) three see Fig.\ref{fig:OVSFTree}. The set of codes generated from the OVSF tree contains the same orthogonal codes as codes generated using Hadamard or Walsh codes, the differences comes from how they are indexed.


\begin{figure*}[htbp]
	\centering
		\includegraphics[width=80mm]{images/OVSFTree.png}
	\caption{An Orthogonal Variable Spreading Factor Tree (OVSF-Tree). In the bit strings defining the OVSF codes a 0 represents +1 and a 1 represents -1.}
	\label{fig:OVSFTree}
\end{figure*}

\subsubsection{Scrambling codes}\label{sec:scramblingCode}
The scrambling codes are used to separate the signals from multiple RBSs or UEs transmitting at the same frequency. The scrambling sequence is a pseudo random noise sequence which, by its own, appears as white noise.
The properties of the scrambling codes are, large impulse response when cross-correlated against itself and small when correlated against any of the other scrambling codes.

The scrambling codes are divided into 512 sets each containing one primary and fifteen secondary codes. The codes are  pseudo random noise sequences and built from a set of Gold sequences $Z_n, n=\lbrace0,1,2,...,2^{18}-2\rbrace$, which are generated from two so called m-sequences $x$ and $y$. The $x$ and $y$ m-sequences and the Gold sequences $Z_n$ are recursively defined as:

\begin{eqnarray*}
 x(i+18) & = & (x(i+7) + x(i)) \bmod 2,\\
 y(i+18) & = & (y(i+10)+y(i+7)+y(i+5)+y(i)) \bmod 2, \\
 z_{n}(i) & = & (x((i+n) \bmod (2^{18} - 1)) + y(i)) \bmod 2, \\
 i & = & \lbrace 0,1,2,..., 2^{18}-20\rbrace , \\
 n & = & \lbrace 0,1,2,...,2^{18}-2\rbrace ,
\end{eqnarray*}
with the following starting conditions for $x$ and $y$ as:
\begin{eqnarray*}
 x(0) & = & 1,\\
 x(\lbrace 1,2,...,17 \rbrace) & = & 0, \\
 y(\lbrace 0,1,2,...,17 \rbrace) & = & 1
\end{eqnarray*}

The scrambling codes $S_n$ are then finally defined as:
$$
S_n(i) = Z_n(i) + j Z_n((i+131072) \bmod (2^{18}-1)),
$$ where $i=\lbrace 0,1,...,38399\rbrace$ and $n = 16*m+k$ where $m$ defines the scrambling code set from $0..511$ and $k$ is equal to zero for primary scrambling codes and else in the range from $1$ to $15$ for the secondary scrambling codes.
 


\subsection{Modulation / demodulation}\label{sec:modulation}
This section focuses on the transformation of the data from bits into chips, ready to be transmitted over the air interface. Figure~\ref{fig:modulation} displays a simplified view of how bits from one channel, are processed into chips.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=160mm]{images/modulation.png}
	\caption{The modulation pipeline from bits to antenna for a single channel}
	\label{fig:modulation}
\end{figure*}


\subsubsection{IQ modulation}\label{sec:IQmodulation}
In the process of IQ modulation, bits are turned into complex symbols. The symbols are produced by dividing the two dimensional IQ space into regions (constellations) representing symbols, where each symbol represents a bit pattern. In QPSK (Quadrature phase-shift keying), which is one of the modulation schemes used in WCDMA, the two dimensional space is divided along the two axes, I and Q, into four regions each representing two bits (00, 01, 11, 10). The diagram in Figure~\ref{fig:QPSKSymbols} illustrates the mapping from bits to symbols for QPSK. Notice that gray-coding is often preferred when mapping bits to symbol constellations, this in order to minimize bit errors caused by symbols wrongfully ending up in a neighbour constellation on the receiver side due to interference.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=60mm]{images/QPSKSymbols.png}
	\caption{Diagram of the mapping from bits to symbols for QPSK}
	\label{fig:QPSKSymbols}
\end{figure*}


\subsubsection{Spreading}
In the spreading process the channelisation code is applied on the symbols. Each symbol is multiplied with each chip in the spreading code.
$$
D = S \times C_{ch,s,c} = S \times [C_{ch,s,c}(0), ..., C_{ch,s,c}(s-1)]; s > 0,
$$ where $S$ is the complex symbol, $C_{ch,s,c}$ is the channelisation code from the OSVF tree with spreading factor $s$ and code number $c$ and $C_{ch,s,c}(n)$ refers to the n:th chip in the sequence $C_{ch,s,c}$. The result $D$ is a sequence of chips with the same length as the spreading factor $s$ of the spreading code $C_{ch,s,c}$.
\subsubsection{Scrambling}
The scrambling process multiplies the chips from the spreading process with the scrambling code. The scrambling code is aligned with the PCCPCH frame start.

\subsubsection{Pulse shaping}
For pulse shaping a root raised cosine (RRC) filter is used with a roll-off factor of $0.22$. The purpose of the RRC filter is to reduce inter symbol interference.

\subsection{Channels}
The channels used in WCDMA are divided into three layers: logical-, transport- and physical- channels . The logical channels mainly carries NAS data and are mapped onto transport channels. The transport channels are then carried over the air interface by the physical channels. This section describes the downlink physical channels~\cite{ref:ts25211} used throughout this thesis project. Figure~\ref{fig:channels} contains a chart of the physical channels covered in this section and their alignment.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/channels.png}
	\caption{Chart of some of the physical channels.}
	\label{fig:channels}
\end{figure*}


\subsubsection{P-SCH}
The primary synchronisation channel (P-SCH) transmits the PSC each first 256 chips of every slot. This channel is not spread or scrambled with channelisation and scrambling codes.

\subsubsection{S-SCH}
The secondary synchronisation channel (S-SCH) transmits a predefined repetitive sequence of 15 SSCs each one transmitted on the first 256 chips of every slot. This channel is not spread or scrambled with channelisation and scrambling codes.

\subsubsection{CPICH}
The Common pilot channel (CPICH) carries pilot information used by the UE to identify the scrambling code of the RBS. It is also used for detecting the phase rotation (Sec.~\ref{sec:phaseRotation}) and for measuring the signal quality. All symbols on the CPICH channel contains IQ data of (1+1j). The CPICH uses channelisation code $C_{ch,256,0}$ \cite{ref:ts25213}

\subsubsection{PCCPCH}
Primary common control physical channel (PCCPCH) carries the broadcast transport channel (BCH), which in terms carries the broadcast control channel (BCCH). PCCPCH uses QPSK modulation and channelisation code $C_{ch,256,1}$ \cite{ref:ts25213}. No information is transmitted the first 256 chips of every slot on PCCPCH.

\newpage

\section{RSSI scan}
A RSSI scan (received signal strength indicator scan) is performed by measuring the energy on a set of frequencies. Frequencies with higher energy levels are potentially better candidates for containing a WCDMA cell. The RSSI measurements done in this thesis is done by calculating the squared magnitude of the received IQ samples.

\newpage
\section{Synchronisation}
This section describes the synchronisation process, derived from the cell search procedure in~\cite{ref:ts25214}. The process is divided into three parts: slot synchronisation, frame synchronisation and scrambling code identification. It is however possible to identify the scrambling code and find slot and frame synchronisation without the first two steps but it makes the process much more complex in terms of computational complexity. Correlating all 512 primary scrambling codes against the received signal, measuring which one producing the largest response on every chip over at least an entire frame would simply be too time consuming. The first steps in the synchronisation procedure eliminates the set of possible scrambling codes down to eight and also detects the frame boundaries so that each possible scrambling code only needs to be correlated using one correlation offset that matches a frame boundary.

\subsection{Slot synchronisation}\label{sec:slotSync}
The first step in the synchronisation process is to acquire slot synchronisation. This is performed by calculating the magnitude of the correlation (Section~\ref{sec:correlation}) of the PSC against the received signal. This process may need to be done a number of times and the result should be accumulated in order to receive proper results that can be trusted as valid. Large peaks indicates the beginning of a slot, see Figure~\ref{fig:pscCorrelation}.


\begin{figure*}[htbp]
	\centering
		\includegraphics[width=120mm]{images/pscCorrelation.png}
	\caption{Illustration of the magnitude of the correlation ($|R[m]|$) of the PSC against the received signal and its usage in order to detect the slot boundaries.}
	\label{fig:pscCorrelation}
\end{figure*}


\subsection{Frame synchronisation}\label{sec:frameSync}
The purpose of the second step is to acquire frame synchronisation and also to detect what scrambling code group that the cell belongs to. This is done by correlating the the 16 SSCs against the 256 first chip of every slot in order to detect a pattern of a repetitive sequence of 15 SSC. The process may need to be performed a number of times over a multiple of 15 slots and the result from each chunk of 15 slots should be accumulated. By taking the SSC with the best match in each of the 15 slots a sequence of 15 SSCs is constructed.
Figure~\ref{fig:receivedSSCSequence} describes the process.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=100mm]{images/receivedSSCs.png}
	\caption{Illustration of the SSC correlation result and the identified SSC sequence.}
	\label{fig:receivedSSCSequence}
\end{figure*}

The detected SSC sequence can then be used to detect the frame boundaries and the scrambling code group for the cell by checking the received sequence against a table, defined in the 3GPP TS25.213~\cite{ref:ts25213}, containing the 64 predefined SSC sequences that defines the scrambling code group. At this point, the start of the received SSC sequence is unknown, therefore it needs to be rotated and for each iteration it needs to be checked against each row of the SSC sequence table. The newly found start of the SSC sequence defines the start of the frame boundaries and the row from the SSC sequence table defines what scrambling code group that the cell belongs to, see Figure~\ref{fig:frameSync}.  

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=120mm]{images/frameSync.png}
	\caption{The detected SSC sequence is measured against the SSC sequence table defined in \cite{ref:ts25213}, containing all the valid SSC sequences.}
	\label{fig:frameSync}
\end{figure*}


Since the slot boundaries should be known by the previous step in the synchronisation process, the 16 SSCs only needs to be correlated against the first 256 chip in every slot, giving 16 correlations each slot.


\subsection{Scrambling code identification}\label{sec:scramblingCodeIdentification}
The final step in the synchronisation process involves detecting the primary scrambling code that the cell is using, this in order to be able to descramble the actual signals transmitted by the cell.

The process of identifying the scrambling code is done by correlating the complex conjugate of the scrambling codes against the received signal starting from the beginning of each frame. The correlation that gives the strongest peak is probably the primary scrambling code used by the RBS. Each scrambling code may need to be correlated against multiple frames and the accumulated result may be used in order to receive a better response. 

Not all 512 scrambling codes needs to be used in the correlation, since the frame synchronisation step identified what scrambling code group that the measured cell belongs to. Therefore only those scrambling codes that belongs to the scrambling code group for the particular cell are relevant to test.

\newpage

\section{Phase rotation}\label{sec:phaseRotation}
When a signal propagates through the air it gets distorted in a couple of ways. One phenomena is phase rotation. Phase rotation may occur as an effect of a frequency error in the receiver. Phase rotation is also necessary, since  without any pilot information, the reference phase is unknown on the receiver side.

The CPICH channel may be used in order to deal with phase rotation, since a known signal $(1+j)$ is constantly being transmitted on the CPICH channel. The difference between the phase of the received CPICH channel and the expected phase $(1+j)$ can be calculated and used in order to rotate the signal back into the correct phase, see Figure~\ref{fig:phaseRotation}.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=60mm]{images/phaseRotation.png}
	\caption{The phase difference $d$ between a received chip $R$, from the CPICH channel, and its expected position $(1+j)$}
	\label{fig:phaseRotation}
\end{figure*}


\newpage

\section{From signal to bits}\label{sec:signalToBits}

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/receiverChain.png}
	\caption{The different processing blocks for transforming the signal into bits for one channel in WCDMA}
	\label{fig:receiverChain}
\end{figure*}

Section~\ref{sec:modulation} describes in short how bits are modulated into a signal that gets transmitted over the radio air interface. This section describes the necessary steps for doing the reverse operation of transforming the signal into bits for a particular channel.

The required steps are the following, Table~\ref{tab:signalToBits_Definitions} contains a listing of the definitions used and Figure~\ref{fig:receiverChain} displays a flowchart of the process (Note that this description is based on a sample rate equal to the chip rate, for higher sample rates the WCDMA codes should be spread with a factor equal to the multiple of the chip rate that is used for the sampling rate. This is necessary in order to align the codes correctly with the received signal):

\begin{table}[ht]
 \begin{center}
  \caption{Definitions}\label{tab:signalToBits_Definitions}
  \begin{tabular}{ | l | l | }
    \hline
      Symbols & Explanation \\ \hline
	  $C_{scr,q}(i)$ & The $i$:th chip of the primary scrambling code number $q$ \\ \hline
	  $C_{ch,a,b}$ & The channelisation code number $b$ with spreading factor $a$ from the OVSF-tree\\ \hline
	  $x^*$ & The complex conjugate of $x$ \\ \hline
  \end{tabular}
 \end{center}
\end{table}



\begin{enumerate}
\item Sample the received signal and perform pulse shaping with a raised root cosine filter with a roll-off factor of $0.22$ producing the samples $R_{0}(n)$ where $n$ defines the chip number and $R_{0}(0)$ is the first chip in a frame. 

\item \label{step:de_scrambling} De-scramble the signal by chip-wise multiplication of the complex conjugate of the identified scrambling code ($C_{scr, q}$) against the chips in $R_{0}(n)$
$$
R_{1}(n) = C^{*}_{scr, q}(n \bmod 38400) R_{0}(n).
$$

\item De-spread the signal by calculating the sum of the chip wise multiplication of the channelisation code $C_{ch,a,b}$ for the wanted channel with the chips, $R_1(n)$ received from step~\ref{step:de_scrambling}, with spreading factor $a$ and channelisation code $b$
$$
R_{2}(n_1) = \sum^{a-1}_{i=0}( C_{ch,a,b}(i)R_{1}(an_1+i) ).
$$

\item At this step it would be possible to measure the phase difference for the CPICH (see Section~\ref{sec:phaseRotation}). If phase rotation has occurred the signal needs to be rotated back in order to decode the other channels. Taking the symbols in $R_2(n_1)$ as input and correct the phase against the CPICH producing the phase corrected symbols, $R_3(n_1)$ as output.

\item Map the chips $R_{3}(n_1)$ from symbols to bits. Different channels may use different modulation techniques. For PCCPCH which carries the BCH QPSK is used (see Section~\ref{sec:IQmodulation}).

\item Done, a sequence of bits can now be obtained for a specific channel.

\end{enumerate}

\newpage

\section{Decoding the broadcast channel}\label{sec:decodingBCH}\label{sec:decodingBCH}
The BCCH is the logical channel containing the broadcast messages transmitted by the RBS. The BCCH is mapped onto the transport blocks (TrBlk) on the BCH transport channel and the BCH is mapped onto the PCCPCH that is transmitted over the air. 

This section describes the mapping from BCH to PCCPCH and how to perform the reverse operation. The process is derived from 3GPP TS 25.212~\cite{ref:ts25212} (Section 4 Multiplexing, channel coding and interleaving
) and TS 25.302~\cite{ref:ts25302} (Annex A (normative): Description of Transport Formats) which describes the process in general for all channels.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/BCCHtoPCCPCH.png}
	\caption{The different steps in mapping the BCCH onto PCCPCH}
	\label{fig:BCCHtoPCCPCH}
\end{figure*}

\subsection{The mapping from BCH onto physical channels}
The following steps maps the BCH onto the PCCPCH (Fig.~\ref{fig:BCCHtoPCCPCH} illustrates the process):
\begin{enumerate}
	\item The data bits from the BCCH are mapped onto BCH TrBlk each of size 246 bits.
	\item A CRC checksum of 16 bits is appended onto each TrBlk, see Section~\ref{sec:CRC}.
	\item Each TrBlk with the appended CRC checksum passes through a convolution coder, see Section~\ref{sec:convolutionCoding}.
	\item Bit interleaving.
	\item Data is passed onwards to the PCCPCH.
\end{enumerate}




\subsection{Cyclic redundancy check}\label{sec:CRC}

The purpose of the Cyclic redundancy check (CRC) is to create a set of bits which can be used on the receiver side to verify that the received bits are correct, although it should be noticed that there is a slight chance that bit errors may be introduced in both the CRC bits and the CRC encoded data, this could make the CRC bit check pass on the receiver side even though the received bits contains errors. There is also the case of when the CRC coded data is intact but bit errors have been introduced in the CRC bits, in that case there is no way of detecting at the receiver side what actually happened. Instead the CRC coded data gets discarded as invalid.

The CRC calculator takes TrBlks as input, calculates and outputs the CRC bit string and finally attaches it at the end of the TrBlk. Figure~\ref{fig:CRC} displays a scheme of the 16-bit CRC calculator, with the generator polynomial of $D^{16} + D^{12} + D^{5} + 1$, that is used to calculate the CRC bits for BCH. The bits from the transport block is inserted into the CRC calculator. During TrBlk insertion the output bits are ignored. The CRC calculator is cleared between each TrBlk by inserting zero bits. The output generated while clearing the CRC calculator is the actual CRC bits that are appended to the TrBlk.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/CRC.png}
	\caption{A scheme of the 16-bit CRC calculator used in WCDMA}
	\label{fig:CRC}
\end{figure*}

\subsection{Convolutional coding}\label{sec:convolutionCoding}
WCDMA uses two different types of forward error correcting codes: Convolution coding and Turbo coding. The purpose of the error correcting codes are to correct bit errors that may have been introduced when data was transmitted over the air interface. For the BCH half-rate (1/2) convolution coding is applied, meaning that one input bit generates two output bits. Figure~\ref{fig:convolutionalCoder} contains a chart of the 1/2 convolution coder used in WCDMA. The encoding machine is a state machine with $2^k$ number of states where $k$ is the number of memory registers holding the current state of the machine (as seen in Fig.\ref{fig:convolutionalCoder}). 


Code blocks are delivered as input to the convolution coding machine one at a time in sequence. Each code block consists of a TrBlk with the appended CRC bits and eight tail bits of zeros. The purpose of the tail bits are to clear the state of the convolution coding machine between each code block.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/convolutionalCoding.png}
	\caption{The half rate convolutional encoder used in WCDMA. Output bits are ordered as \texttt{Output\_0}, \texttt{Output\_1}, \texttt{Output\_0}, \texttt{Output\_1},..., \texttt{Output\_0}, \texttt{Output\_1}}
	\label{fig:convolutionalCoder}
\end{figure*}


\subsection{Convolution decoding}
The output from the convolution coder describes a path through a trellis diagram, where the entire set of states of the encoding machine makes up the columns of the diagram. The number of columns is equal to the number of bits inserted to the encoding machine plus one (the start state). The transition from one state to another is based on the current state and the input. Decoding a convolutionally encoded string is done by finding the path through the trellis diagram, that best matches the encoded string.

As an example, the convolution coder in Figure~\ref{fig:simpleCCM} has encoded the bit string '1001' which generates the output '11011111'. Figure~\ref{fig:trellisDiagram} displays a trellis diagram of the encoded bit string and the path through the diagram that represents the correct decoding of the encoded string.

Going through and calculating how well each path matches the bit string that should be decoded is a complex procedure in terms of computational power. Therefore, in order to speed up the process, it is necessary to make some decision on which paths that are more likely to contain the proper solution. A common way of doing this is often referred to as Viterbi decoding\cite{ref:viterbiAlgorithm}. The principle behind a Viterbi decoder is that whenever two paths meet at the same state in the trellis diagram, discard the path with the lowest match. For further reading about the Viterbi Algorithm the tutorial introduction \emph{The Viterbi Algorithm}\cite{ref:vaTutor} is recommended.

In WCDMA, since the start state of the encoding machine is known to be zero for each coding block delivered to the encoding machine, all paths originating from the other starting states are not needed to be included in the set of paths that may make up the original code block, neither any paths not ending with eight decoded zero bits.

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=60mm]{images/SimpleCCM.png}
	\caption{A scheme of a simple convolution encoder.}
	\label{fig:simpleCCM}
\end{figure*}


\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/TrellisDiagram.png}
	\caption{A Trellis diagram displaying the correct path and all invalid paths starting at state '00'}
	\label{fig:trellisDiagram}
\end{figure*}

\subsection{Interleaving}

A property of convolutionally encoded bit strings are that the decoder works better if the errors that may have been introduced into the bit string are somewhat evenly distributed~\cite{ref:interleavingProperties}. Therefore a set of bit interleaving operations are applied before the encoded blocks are transmitted over the air. The BCH is transmitted over two radio frames and the first interleaver spreads equally many bits from each radio frame to the other by using the following formula on each BCH encoded code block:

The output bits from the convolution coder, for each encoded code block, are denoted as $b_n$ where $n = 1$, $2$, $3$, ... , $i$ where $i$ is the number of output bits produced by the convolution coder for one code block, for BCH  $i = 540$. A $R_1 \times C_1$ matrix $M_1$ where $R_1 = 270$ and $C_1 = 2$ is filled with the bits $b_n$ row by row.


\[ M_1 = \left[ 
\begin{array}{ccccc}
b_1 & b_2 \\
b_3 & b_4 \\
b_5 & b_6 \\
... & ... \\
b_{539} & b_{540}
\end{array} \right].\] 

The first interleaving step then outputs the bits column by column:
$b_1$, $b_3$, $b_5$, ... , $b_{539}$, $b{_2}$, $b_{4}$, $b_{6}$, ... , $b_{540}$, where the first 270 bits belongs to the first radio frame in the TTI and the second 270 bits belongs to the second radio frame in the TTI.\\


\noindent The second interleaving step spreads the bits within each radio frame. For bits from the BCH the following formula is used:

Let the bits in each radio frame sent to the second interleaving step be denoted as $c_n$ where $n = 1$, $2$, $3$, ... , $j$ where $j = 270$. A $R_2 \times C_2$ matrix $M_2$ where $R_2 = 9$ and $C_2 = 30$ is filled with the bits $c_n$ row by row. \\

\[ M_2 = \left[ 
\begin{array}{ccccc}
c_1    & c_2    & c_3    & ... & c_{30} \\
c_{61} & c_{62} & c_{63} & ... & c_{60} \\
c_{91} & c_{92} & c_{93} & ... & c_{90} \\
...    & ...    & ...    & ... & ...    \\
c_{241}& c_{242}& c_{243}& ... & c_{270}\\
\end{array} \right].\] 

A new matrix $M_{2p}$ is then defined as an inter column permutation of the matrix $M_2$ according to the following pattern:\\ $M_{2p} = [A_0$, $A_{20}$, $A_{10}$, $A_{5}$, $A_{15}$, $A_{25}$, $A_{3}$, $A_{13}$, $A_{23}$, $A_{8}$,  $A_{18}$, $A_{28}$, $A_{1}$, $A_{11}$, $A_{21}$, $A_{6}$, $A_{16}$, $A_{26}$, $A_{4}$, $A_{14}$, $A_{24}$, $A_{19}$, $A_{9}$, $A_{29}$, $A_{12}$, $A_{2}$, $A_{7}$, $A_{22}$, $A_{27}$, $A_{17}]$, \\where $A_{0, 1, 2, ... , 29}$ are the columns of matrix $M_2$ from left to right.

The output bits from the second interleaving step are then read out column by column from the matrix $M_2p$.

\subsection{The BCH data bits}
Finally when the entire process of reading bits on the PCCPCH (Section~\ref{sec:signalToBits}) and the process of decoding the PCCPCH bits turning them into BCH bits (Section~\ref{sec:decodingBCH}), the BCH data bits are revealed.

The BCH data bits carries the broadcast messages and the System Frame Number (SFN) of the current cell. The SFN is the first 12 bits of every BCH TrBlk and the rest of the data bits carries the BCCH messages. The BCCH messages basically consists of a set of different data blocks. The Master Information Block (MIB) describes when the other System Information Blocks (SIBs) are scheduled. The SIBs contains the actual information about the current cell.



\newpage

\section{Implementation}
This section covers the implementation, the design of the software and implementation specific issues.


\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/receiver.png}
	\caption{A scheme of the signal processing blocks of the receiver chain.}
	\label{fig:receiver}
\end{figure*}

\subsection{Concept}
The implemented software consists of two signal processing blocks. The blocks are combined with other signal processing blocks in a flow chart that makes up the receiver. Figure~\ref{fig:receiver} displays a scheme of the receiver chain. The implemented slot Sync block and the Resampler blocks are described further within this section. The other blocks in the figure are standard GNU radio blocks.  


\subsection{GNU Radio blocks}
Two signal processing blocks were implemented for the WCDMA cell synchronisation software. A resampler block that takes samples of some sample rate as input and linearly interpolates between the incoming samples producing new samples with some other sample rate as output. This was needed since the N-210 device was not able to sample at a multiple of the WCDMA chip rate. 

The second block makes up the entire WCDMA receiver. It consists of four different states: \texttt{WAIT\_ON\_RADIO}, \texttt{FIND\_SLOT\_SYNC}, \texttt{FIND\_FRAME\_SYNC} and \texttt{IN\_SYNC}. The slot sync block contains pre generated lookup tables of the PSC, SSCs and the scrambling code group table containing the SSC sequences for the different scrambling code groups. The scrambling codes are generated online, by using pre-calculated start values for each primary scrambling code and then generating the rest of the chips in the scrambling sequences on the fly, this due to the length of the sequences. The codes and how they are generated are described in Sections~\ref{sec:psc}, \ref{sec:ssc} and \ref{sec:scramblingCode}.

\begin{itemize}
\item\texttt{WAIT\_ON\_RADIO}, at this state the signal processing block only waits for a predefined number of samples in order to make sure that the radio has become stable. When done, it changes state into \texttt{FIND\_SLOT\_SYNC}.

\item\texttt{FIND\_SLOT\_SYNC}, at this state the signal processing block searches for the slot boundaries by correlating the PSC against the received signal in order to detect slot boundaries (Section~\ref{sec:slotSync}). To improve the slot boundary detection, the correlation is performed for the duration of 3 frames and the result is accumulated in order to improve the correlation peaks.

This is performed by, for each new sample that is arriving to the signal processing block, calculating the sum of the chip wise multiplication of the PSC and the latest received samples. The result is accumulated in a buffer, $B_{sbAcc}$, with length equal to the number of samples per slot $l$, in this case 5120. The result is stored at position $i_{sample}$, where $i$ is the current sample number. After $3 \times 15 \times l$ number of samples (three frames) the index $i_{sBound}$ of the highest accumulated value in the buffer $B_{sbAcc}$ is calculated. The slot boundaries can now be considered to start on each sample where the following condition is met, $((s+511) \bmod l) = i_{sBound}$ where $s$ is the sample number. The addition of $511$ comes from fact that the index $i_{s_Bound}$ is placed at the end of the PSC correlation, and each new slot starts at the beginning of the PSC.



\item\texttt{FIND\_FRAME\_SYNC}, at this state the signal processing block tries to detect the frame boundaries and tries to identify the scrambling code group (Section~\ref{sec:frameSync}). On success it switches state into \texttt{IN\_SYNC} and in case of failure to detect frame boundaries or scrambling code group it goes back to state \texttt{WAIT\_ON\_RADIO}, to try the same procedure again.

At the start of each slot 512 samples are stored away in a buffer $B_{s-sch}$, capturing the S-SCH. The sixteen SSCs are then correlated against the buffer $B_{s-sch}$ at offset zero in order to decide which SSC with the best match in each slot. The result is accumulated over seven frames before deciding which SSC sequence the cell is using. The SSC sequence is then checked against a table containing the valid SSC sequences for each scrambling code group.

\item\texttt{IN\_SYNC}, when in this state the slot- and frame- boundaries and the scrambling code group have been successfully detected. In this state the signal processing block starts to identify the primary scrambling code for the cell, as described in Section~\ref{sec:scramblingCodeIdentification}. Once detected it starts receiving the PCCPCH bits (see Section~\ref{sec:signalToBits}). Meanwhile in this state, since the samples delivered to the block may drift in time with respect to how they are transmitted from the RBS, some simple mechanism is needed in order to keep slot and frame synchronisation. This is done by correlating the PSC around the detected slot boundaries in order to detect if the chips are drifting in time. If this occurs it is corrected by inserting or removing extra chips. Received PCCPCH frames are stored away in an array for offline processing, since the decoding of the BCH is too time consuming to be performed in real time by software running on a standard computer at the time of the implementation.
\end{itemize}

\subsection{Fitting it all together}
Figure~\ref{fig:receiver} shows the resampler block and the cell sync block together with the rest of the receiver chain. A python script launches the application and sets the frequency. It then polls the cell sync block for information about the number of synchronisation tries, and if it has finished reading the PCCPCH frames. If a defined number of synchronisation tries has been done without successfully reading the PCCPCH frames the application terminates. When all PCCPCH frames has been successfully read by the slot sync block, the receiver chain is stopped and the decoding of the BCH is handled by the python script as explained in Section~\ref{sec:decodingBCH}.

\newpage

\section{Results}

\subsection{Receiver performance}
%The implemented RSSI-scan only detects potential cells with good signal strength (more then -75 dBm / 3.84 MHz). This has been tested by plugging in the receiver against WCDMA transmitting hardware.

%Performance measurements on the RSSI scan were performed in lab environment,
The RSSI scan performance were measured in a lab environmet, scanning through the frequency range from $2.126$ GHz to $2.158$ GHz on a $200$ kHz raster with one cell located at $2.14$ GHz. With a cell power of $-90$ dBm $/$ $3.84$ MHz the frequency containing the cell is placed around the first quartile in the frequency ranking list from the RSSI scan. Raising the cell power to $-75$ dBm $/$ $3.84$ MHz places the cell frequency near the top of the ranking list.

%Measurements performed on the RSSI scan functionality performed in lab environment when scanning through the frequency range from $2.126$ GHz to $2.158$ GHz on a $200$ kHz raster with one cell located at $2.14$ GHz with a cell power of $-90$ dBm $/$ $3.84$ MHz  the frequency containing the cell is placed around the first quartile. Raising the cell power to -70 dBm / 3.84 MHz places the frequency containing the cell near the top of the ranking list.
%This might be caused by that the noise level in the radio receiver being to high. This might also be the reason of why good radio conditions are needed in order to correctly decode the BCH without CRC errors. Synchronising against a cell in terms of determining the scrambling code seems to be more resistant to this and is possible in radio environments of lesser quality.

The WCDMA receiver is capable of decoding BCH data from live cells. In a simulated lab environment the WCDMA receiver has been used to decoding BCH data on power levels around -115 dBm / 3.84 MHz although on power levels below -110 dBm / 3.84 MHz decoding problems starts to arrive quite frequently Figure~\ref{fig:performanceGraphWithFilter} shows the measurement tests on the different power levels. On live networks no detailed performance measurements has taken place, although the receiver has been able to decode the BCH data from the live cells that have been tested. It should also be noticed that the receiver only works under static conditions. This is because of no functionality for continuously monitoring and tracking peaks (by continuously correlating the scrambling code against the received signal). That functionality would probably be too computationally expensive to perform in software. Figure~\ref{fig:pscOnce} contains charts of PSC correlations performed against a live cell and against the lab equipment and Figure~\ref{fig:cpichSymbol} displays plots of the received CPICH symbols in live and lab environment. Figure~\ref{fig:cpichSymbolRotated} displays the rotated CPICH symbols. 

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/psc_conv_once.png}
	\caption{Plot of the magnitude of the correlation ($|R[m]|$) of the PSC against the received signal during slot synchronisation.}
	\label{fig:pscOnce}
\end{figure*}

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/cpichrotation.png}
	\caption{Plots of the received CPICH symbols.}
	\label{fig:cpichSymbol}
\end{figure*}

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/rotated_cpich.png}
	\caption{Plots of the rotated CPICH symbols.}
	\label{fig:cpichSymbolRotated}
\end{figure*}

\newpage
\newpage
During the development of the receiver, the Raised Root Cosine (RRC) filter unintentionally was left unconfigured, resulting in the filter having none or minimum impact. Configuring the RRC filter resulted in a great performance boost. From having trouble with reading the BCH and synchronising against cells with power levels below -80 dBm / 3.84 MHz to having no problem at power levels below -100 dBm / 3.84 MHz. Figure~\ref{fig:performanceGraphWithNoFilter} and \ref{fig:performanceGraphWithFilter} shows performance graphs of the receiver, before and after the RRC filter setup. The performance data were collected by examining the results from six consecutive test runs of the receiver software on each power level. 

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/performanceGraphWithNoFilter.png}
	\caption{Performance graph of the receiver for different power levels, before RRC filter setup.}
	\label{fig:performanceGraphWithNoFilter}
\end{figure*}

\begin{figure*}[htbp]
	\centering
		\includegraphics[width=140mm]{images/performanceGraphWithFilter.png}
	\caption{Performance graph of the receiver for different power levels, after the RRC filter setup.}
	\label{fig:performanceGraphWithFilter}
\end{figure*}

\newpage

\subsection{Implementation discussion and details}\label{sec:impDetailsAndDiscussion}

WCDMA places high, real time and computational demands, even for the most simple receiver. The high chip rate enforces a high sampling rate. The descrambling and despreading process requires a fair amount of computational power. Decoding symbols on one signal path only, requires $38.4$ M floating point operations per second (see Table~\ref{tab:computationalComplexity}), without dealing with phase correction and other tasks. The software receiver described in this document is using a sample rate of twice the chip rate and therefore the amount of flops are doubled for the same operation. Taking this into account, a full blown CPU based software WCDMA receiver is not very likely an ideal solution.

\begin{table}[ht]
 \begin{center}
  \caption{Computational cost of common WCDMA operations}\label{tab:computationalComplexity}
  \begin{tabular}{ | l | l | }
    \hline
      Operation & Cost \\ \hline
      One complex multiplication (cMul) & $4$ Mul $+$ $4$ Add\\ \hline \hline
	  Descramble one chip & $1$ cMul\\ \hline
	  De-channelisation on one chip & $2$ mul\\ \hline\hline
	  Total (descramble and de-channelise one chip) & $10$ floating point operations (flop)\\ \hline\hline
	  Decode one slot & $2560 \times 10 = 25600$ flop\\ \hline
	  Decode one frame & $25600\times 15 = 384000$ flop\\ \hline
	  Decode one signal path for one second & $384000 \times 100 = 38.4$ Mflop/s\\ \hline	  
  \end{tabular}
 \end{center}
\end{table} 
 
 %$100 \times 15 \times 2560   = 3.84$~M multiplications of complex numbers per second are needed. When despreading one channel on that path an additional $3.84 \times 2$~M multiplications per second needs to be executed. This results in at least $7.68 \times 10$~M floating point operations per second\footnote{One complex multiplications equals four real multiplications and four real additions and the despreading consists of two additional real multiplications}
The goal of this thesis project, to implement a software WCDMA receiver with capability of receiving broadcast messages from a WCDMA cell, is much likely how far it is possible to take this in pure software today, with signal processing being performed on a standard CPU. Although worth mentioning is that the USRP radio used in this project contains an on-board FPGA, so it would probably be possible to implement high computationally costly parts in hardware. 

The solution presented in this thesis only performs parts of the tasks in almost real time, the caption of the PCCPCH bits. The rest of the decoding is performed offline. The term almost real time is used since the implementation, running on the hardware used during development, is not processing samples in the same phase that they arrive. The samples are actually arriving faster then what the implementation can process. The implementation works since large sampling buffers are used and the caption of the PCCPCH bits is finished before the buffers are overrun.

One of the first ideas of the implementation was to write modular signal processing blocks for GNU Radio for the different tasks eg. correlation, de-scrambling, de-spreading and so on and combine these into a receiver that performs synchronisation against a WCDMA cell. This early showed to be a bad decision since a lot of CPU cycles are wasted only for pushing the samples around the flowchart. 

Throughout the WCDMA receiver, different constant values are used for filter settings, number of accumulations etc. Nearly no effort has been made to tune these constants, in order to improve performance. Most of the constants were simply hand picked during the implementation phase, so there is probably some optimisations that can be done by simply tweaking the different constants. 

\subsection{Conclusions and discussion}%{Conclusions}

Traditional radio hardware development is an expensive and cumbersome process, especially when compared to writing software for general purpose CPUs. Software Defined Radio technology provides an affordable solution for radio development, even in terms of hobby development. Software Defined Radios are also easy to extend and update, all that is required in order to add new features or improvements, is to change or adapt the software.

Some key benefits of SDR are:
\begin{itemize}
\item A common platform allows new products to be introduced to the market more quickly.
\item From a common code base, software components and radio devices can be re-used, producing many different products and reducing development costs.
\item A flexible system, that is well suited for research and development.
\item Increased lifetime of radio products, since software upgrades may reduce the need of entirely changing the hardware.
\end{itemize}

However, Software Defined Radio do have some drawbacks in terms of computational power and speed. Specially designed hardware will always outperform software in terms of speed, and probably also with respect to power usage. As stated in Section~\ref{sec:impDetailsAndDiscussion} the goal of this project, to receive broadcast WCDMA data, was accomplished. But not entirely in full real time due to lack of computational power. Never the less, Software Defined Radio will probably be more and more common due to it's flexibility, and combined with hardware accelerated special computations (eg. GPU or FPGA usage) the loss in computational power might not be that large.

So the final conclusion is that although reception of WCDMA data in pure software with GNU radio is not the most ideal solution, the goal of the thesis project was fulfilled; and probably within this, the strength of Software Defined Radio lies, as a fast and easy prototyping/research development kit to be used in order to try out concepts for signal processing, traditionally only performed in hardware, which later on may be realised onto real hardware or FPGA.

\subsection{Future work}
The work covered in this report only covers a bare minimum for the reception of WCDMA data and should only be seen as a proof of concept. A real receiver should contain lots of extra functionality eg. possibility to detect and combine different signal paths (RAKE receiver) and some automatic frequency correction (AFC). There exists a tonne of other vital components in order to make up a receiver with good performance.

It would be interesting to investigate the possibility of performing signal processing calculations on a graphics processing unit (GPU). Receiving WCDMA data is computationally expensive in terms of complex floating point operations. Today GPUs are good at performing lots of floating point operations per second. It would be an interesting approach to see how much of the receiver chain work that is possible to perform in real-time on this type of hardware. An interesting example of GPU usage to accelerate signal processing tasks within a SDR environment is the mobile WiMAX terminal presented in the article \emph{SDR system using graphics processing unit}\cite{ref:GPUExample}. The final system was capable of handling up to 2~Mbps throughput. However, it is speculated that it is capable of handling IEEE 802.11.

Another approach would be to investigate how far it is possible to implement a WCDMA receiver/transmitter using the on-board FPGA. An interesting example of this is the OpenBTS\cite{ref:openBTS} project which is an implementation of the 2G GSM air interface and is a low cost solution which makes it possible to make Voip calls with traditional GSM phones using a USRP connected to a computer running the OpenBTS implementation.

\subsection{Lessons learned}
WCDMA employs lots of techniques within different fields from both radio- and computer- science. For me as a bachelor degree student in computer science, with nearly zero previous experience with radio and coding techniques, this has been a interesting voyage from IQ samples up to forward correcting codes and all the stages in between. WCDMA is a complex air interface with a huge standard defined by the 3GPP. The standard is also written with respect to people with knowledge in mobile communication and often only tells how information is coded/sent, and assuming that the reader have the knowledge to do the reverse operation by themselves. A lot of my effort has been placed on first finding information in the specification, understanding it and then to implementing it.

\newpage
\section{Abbreviations}
\begin{center}
  \begin{tabular}{l l}
  	  2G		& Second generation\\
      3G		& Third generation\\
      3GPP  	& 3rd Generation Partnership Project\\
      AS		& Access stratum\\
      BCCH  	& Broadcast control channel\\
      BCH   	& Broadcast channel\\
      CDMA  	& Code division multiple access\\
      CN		& Core network\\
      CPICH		& Common pilot channel\\
      DL		& Downlink\\
      EDGE		& Enhanced data rates for GSM evolution\\
      FDD 		& Frequency division duplex\\
      FDMA 		& Frequency division multiple access\\
      GNU		& GNU's Not Unix\\
      GSM		& Global system for mobile communications\\
      MAC		& Medium access control\\
      NAS		& Non access stratum\\
      OVSF 		& Orthogonal variable spreading factor\\
      P-SCH		& Primary synchronisation channel\\
      PCCPCH 	& Primary common control physical channel\\
      PSC		& Primary synchronisation code\\
      RAT		& Radio Access Technology\\
      RBS		& Radio base station\\
      RLC		& Radio link control\\
      RNC		& Radio network controller\\
      RRC		& Radio resource control\\
      RSSI 		& Received signal strength indicator\\
      S-SCH		& Secondary synchronisation channel\\
      SDR		& Software defined radio\\
      SFN		& System frame number\\
      SSC		& Secondary synchronisation code\\
      TDD 		& Time division duplex\\
      TDMA 		& Time division multiple access\\
      UE		& User equipment\\
      UL		& Uplink\\
      UMTS 		& Universal mobile communications system\\
      USRP		& Universal software radio peripheral\\
      UTRAN 	& UMTS terrestrial radio access network\\    
      WCDMA 	& Wideband code division multiple access\\
  \end{tabular}  
\end{center}

\newpage

\begin{thebibliography}{99} %ändra 9 till 99 om fler än 9 referenser
  \bibitem{ref:SDRBook}
  Walter Tuttlebee, Eduardo Ballesteros, Paul Bender, Wayne Bonser, Rainer Bott, Didier Bourse, Pubudu Chandrasiri, Kate Cook, Markus Dillinger, Gavin Ferris, Mike Grable, Shinichiro Haruyama, David Hislop, Ryuji Kohno, Ruediger Leschhorn, Allan Margulies, Carlos Martınez, Joseph Mitola III, Stephen O’Fee, John D. Ralston,
  \emph{Software Defined Radio - Origins, Drivers and International Perspectives},
  John Wiley \& Sons,
  2002,
  ISBN 0470 84464 7.

  \bibitem{ref:convergence}
  Bannister Mather Coope,
  \emph{Convergence Technologies for 3G Networks IP, UMTS, EGPRS and ATM}.
  WILEY,
  2005.
 
  \bibitem{ref:WCDMA}
  Richardson,
  \emph{WCDMA Design Handbook}.
  University Press, Cambridge,  
  2006.

  \bibitem{ref:ts25201}  
  3rd Generation Partnership Project,
  Technical Specification 25.201 - \emph{Physical layer - general description},
  3GPP TS 25.201 V7.3.0 (2007-05).
%technical specification of the WCDMA physical layer:
%25.201 Physical layer - general description (V7.3.0, 2007-05)

  \bibitem{ref:ts25211}
  3rd Generation Partnership Project,
  Technical Specification 25.211 - \emph{Physical channels and mapping of transport channels onto physical channels (FDD)},
  3GPP TS 25.211 V9.2.0 (2010-09).
%25.211 Physical channels and mapping of transport channels
%onto physical channels (FDD) (V9.2.0, 2010-09)

  \bibitem{ref:ts25212}
  3rd Generation Partnership Project,
  Technical Specification 25.212 - \emph{Multiplexing and channel coding (FDD)},
  3GPP TS 25.212 V7.7.0 (2007-11).  
%25.212 Multiplexing and channel coding (FDD) (V7.7.0,2007-11)

  \bibitem{ref:ts25213}
  3rd Generation Partnership Project,
  Technical Specification 25.213 - \emph{Spreading and modulation (FDD)},
  3GPP TS 25.213 V9.2.0 (2010-09).
%25.213 Spreading and modulation (FDD) (V9.2.0, 2010-09)

  \bibitem{ref:ts25214}
  3rd Generation Partnership Project,
  Technical Specification 25.214 - \emph{Physical layer procedures (FDD)},
  3GPP TS 25.214 V7.12.0 (2009-05).
%25.214 Physical layer procedures (FDD) (V7.12.0, 2009-05)

  \bibitem{ref:ts25215}
  3rd Generation Partnership Project,
  Technical Specification 25.215 - \emph{Measurements (FDD)},
  3GPP TS 25.215 V9.2.0 (2010-03).
%25.215 Measurements (FDD) 

  \bibitem{ref:gnuradioweb}
  GNU Radio website,
  http://www.gnuradio.org

  \bibitem{ref:ettusweb}
  Ettus Research website,
  http://www.ettus.com


  \bibitem{ref:SDRBook2}
  Walter Tuttlebee, Marc Beach, Stephen Blust, Brad Brannon, Darren K. Brock, Paul Bucknell, John Chapin, Chris Cloninger, Mark Cummings, Dimitrios Efstathiou, Gerhard Fettweis, Paul Hendriks, Tim Hentschel, Bahram Honary, Friedrich Jondral, David Lund, Paul Master, John MacLeod, Joseph Mitola III, Klaus Moessner, Steve Pitchers, Bob Plunkett, Paul Warr, Ed Willink, Zoran Zvonar, 
  \emph{Software Defined Radio - Enabling Technologies},
  John Wiley \& Sons,
  2002,
  ISBN 0-470-84600-3.


  \bibitem{ref:WIF}
  The Wireless Innovation Forum website, http://www.wirelessinnovation.org
  
  \bibitem{ref:SDRDef}
  \emph{SDRF Cognitive Radio Definitions}, SDRF-06-R-0011-V1.0.0, 8 Nov 2007, URL(2013-06-08): http://groups.winnforum.org/d/do/1585
  
  \bibitem{ref:IQSignals}
  National Instruments Measurement Fundamentals series,
  \emph{What is I/Q Data?}.
  National Instruments webpage (2011-05-20),\\ http://zone.ni.com/devzone/cda/tut/p/id/4805

%  \bibitem{ref:ts25213}
%  3rd Generation Partnership Project,
%  \emph{Technical Specification 25.213}.
%  3GPP TS 25.213 V8.4.0 (2009-03)

  \bibitem{ref:3gppweb}
  3GPP website,
  http://www.3gpp.org

  \bibitem{ref:correlation}
  Steven W. Smith,
  \emph{The Scientist and Engineer's Guide to Digital Signal Processing}, 
  1997-1998, For more information visit the book's website at: www.DSPguide.com

%  \bibitem{ref:ts25212}
%  3rd Generation Partnership Project,
%  \emph{Technical Specification 25.212}.
%  3GPP TS 25.212 V7.0.0 (2006-03)
          
  \bibitem{ref:ts25302}
  3rd Generation Partnership Project,
  \emph{Technical Specification 25.302}.
  3GPP TS 25.302 V3.6.0 (2000-09)
  
  % new references
  \bibitem{ref:viterbiAlgorithm}
  Viterbi, A.J., Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Transactions on Information Theory, April
1967; IT - 13 (2) : pp. 260 - 269.

  \bibitem{ref:vaTutor}
  M. S. Ryan, G. R. Nudd,
  \emph{The Viterbi Algorithm}
  Department of Computer Science, University of Warwick, Coventry,
  1993

  \bibitem{ref:interleavingProperties}
  Andrea Goldsmith,
  \emph{Wireless Communications},
  Chapter 8.8.2 Convolutional Coding with Interleaving,
  Cambridge University Press,
  2005
  
  \bibitem{ref:GPUExample}
  J.Kim, S.Hyeon, S. Choi,
  \emph{SDR system using graphics processing unit},
  IEEE Communications Magazine, pp. 156-168, March 2010.

  \bibitem{ref:openBTS}
  OpenBTS,
  http://gnuradio.org/redmine/projects/gnuradio/wiki/OpenBTS (2012)
  
\end{thebibliography}




\end{document}
